package demo1;

import java.util.Scanner;

public class Main {

    //
    public static void swap(char[] s, int i, int j){
        char tmp = s[i];
        s[i] = s[j];
        s[j] = tmp;
    }

    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        int q = in.nextInt();

        while(q-- != 0){
            char[] s = in.next().toCharArray();
            int n = s.length;

            for(int i = n - 1; i >= 0; i--){
                if((s[i] - '0') % 2 == 0){
                    swap(s, i, n - 1);
                    break;
                }
            }
            if((s[n - 1] - '0') % 2 == 0){
                System.out.println(s);
            }else{
                System.out.println(-1);
            }
        }
    }

    //
    public static int N = 15;
    public static int n, ret;
    public static boolean[] vis = new boolean[N];
    public static int[] arr = new int[N];

    public static void dfs(int pos){
        if(pos == n + 1){  //找到一种合法结果
            ret++;
            return ;
        }

        for(int i = 1; i <= n; i++){
            if(vis[i] == true) { continue;}  //剪枝  i 号队员已经放过了
            if(vis[arr[i]]) { return ;}  //剪枝
            vis[i] = true;  //相当于已经放上 i 号队员
            dfs(pos + 1);
            vis[i] = false;  //回溯  恢复现场
        }
    }

    public static void main2(String[] args){
        Scanner in = new Scanner(System.in);
        n = in.nextInt();

        for(int i = 1; i <= n; i++){
            arr[i] = in.nextInt();
        }

        dfs(1);
        System.out.println(ret);
    }

    //
//    public class Solution {
//
//        int ret = -1010;
//
//        public int maxPathSum (TreeNode root) {
//            dfs(root);
//            return ret;
//        }
//
//        public int dfs(TreeNode root){
//            if(root == null) { return 0;}
//
//            int l = Math.max(0, dfs(root.left));  //左子树为根的最大路径和
//            int r = Math.max(0, dfs(root.right));  //右子树为根的最大路径和
//
//            ret = Math.max(ret, root.val + l + r);  //经过 root 的最大路径和
//
//            return root.val + Math.max(l, r);
//        }
//    }
}
